# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/6/12
# @File : 快速幂求余.py

class Solution(object):
    def maxProductAfterCutting(self, length):  # 贪心，数论
        """
        :type length: int
        :rtype: int
        """
        if (length <= 3): return 1 * (length - 1)#小于等于3的为一种情况
        n = length//3 -1
        x = 3
        rem = 1
        p = 1000000007
        while(n):
            if(n%2==1):rem = rem*x % p
            x = x*x %p
            n = n//2
        if (length % 3 == 0): return (rem*3)%p#刚好是3的倍数，直接看有多少个3，让他们相乘
        if (length % 3 == 1): return  (rem*4)%p#余1的情况：不能承，拿最后一个3 出来，构成2*2，因为2*2>3*1
        if (length % 3 == 2): return (rem*2*3)%p#余2的情况，最后乘2就是

if __name__ == '__main__':
    a = Solution()
    b = a.maxProductAfterCutting(8)
    print(b)